package leetcode_day._2021._202109._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/12 22:28
 * 有效的括号字符串
 * 算法：模拟
 * l 表示左括号的最小值，r 表示左括号的最大值
 * 当前字符是左括号时，l 和 r 都 +1
 * 右括号时，l 和 r 都 -1
 * * 时，l--，r++，
 * * 可以表示左括号和右括号，最少的可以最少，最多的可以最多
 */
public class _12_678 {
    public static void main(String[] args) {
        System.out.println(new _12_678().checkValidString("(*)"));
    }

    public boolean checkValidString(String s) {
        int l = 0, r = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                l++;
                r++;
            } else if (c == ')') {
                l--;
                r--;
            } else {
                l--;
                r++;
            }
            l = Math.max(l, 0);
            // 右括号太多，r 为负数
            if (l > r) return false;
        }
        return l == 0;
    }

}
